<?php

/**
 * 深度优先遍历
 */
class Node
{
    public $lift;
    public $right;
    public $value;
    
    public function __construct($value)
    {
        $this->value = $value;
    }
}

class DFS
{
    /**
     * 前序遍历（递归）
     */
    public function recursionPreorder($root)
    {
        static $res = array();
        if (!is_null($root))
        {
            $function = __FUNCTION__;
            $res[] = $root->value;
            $this->$function($root->lift);
            $this->$function($root->right);
        }
        return $res;
    }
    
    /**
     * 前序遍历（非递归）
     */
    public function preorder($root)
    {
        $res = array();
        $splstock = new SplStack();
        while ( !is_null($root) || !$splstock->isEmpty())
        {
            while ( !is_null( $root))
            {
                $splstock->push($root);
                $res[] = $root->value;
                $root = $root->lift;
            }
            
            $root = $splstock->pop();
            $root = $root->right;
        }
        
        return $res;
    }
    
    /**
     * 中序遍历（递归）
     */
    public function recursionMidorder($root)
    {
        static $res = array();
        if (!is_null($root))
        {
            $function = __FUNCTION__;
            $this->$function($root->lift);
            $res[] = $root->value;
            $this->$function($root->right);
        }
        
        return $res;
    }
    
    /**
     * 中序遍历(非递归)
     */
    public function midorder($root)
    {
        $res = array();
        $splstock = new SplStack();
        while( !is_null($root) || !$splstock->isEmpty())
        {
            while ( !is_null($root) )
            {
                $splstock->push($root);
                $root = $root->lift;
            }
            
            $root  = $splstock->pop();
            $res[] = $root->value;
            $root  = $root->right;
        }
        
        return $res;
    }
    
    /**
     * 后序遍历(递归)
     */
    public function recursionPostorder($root)
    {
        static $res = [];
        if (!is_null($root))
        {
            $function = __FUNCTION__;
            $this->$function($root->lift);
            $this->$function($root->right);
            $res[] =  $root->value;
        }
        
        return $res;
    }
    
    /**
     *
     */
}

$a = new Node(10);
$b = new Node(8);
$c = new Node(12);
$d = new Node(7);
$e = new Node(9);
$f = new Node(11);
$g = new Node(13);

$a->lift    = $b;
$a->right   = $c;
$b->lift    = $d;
$b->right   = $e;
$c->lift    = $f;
$c->right   = $g;

$dfs = new DFS();
$res = $dfs->recursionPreorder($a);
echo 'DFS先序遍历(递归)'.implode('-',$res).PHP_EOL;

$res = $dfs->preorder($a);
echo 'DFS先序遍历(非递归)'.implode('-',$res).PHP_EOL;

$res = $dfs->recursionMidorder($a);
echo 'DFS中序遍历(递归)'.implode('-',$res).PHP_EOL;

$res = $dfs->midorder($a);
echo 'DFS中序遍历(非递归)'.implode('-',$res).PHP_EOL;

$res = $dfs->recursionPostorder($a);
echo 'DFS后序遍历(递归)'.implode('-',$res).   PHP_EOL;

